#include <iostream>
#include <vector>

using namespace std;

class Solution
{
    const int mod = 1'000'000'007;

public:
    int kConcatenationMaxSum(vector<int> &arr, int k)
    {
        vector<int> prefix(arr.size() + 1);
        prefix[0] = 0;
        int max_prefix = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            prefix[i + 1] = prefix[i] + arr[i];
            max_prefix = max(max_prefix, prefix[i + 1]);
        }
        vector<int> suffix(arr.size() + 1);
        suffix[arr.size()] = 0;
        int max_suffix = 0;
        for (int i = arr.size() - 1; i >= 0; i--)
        {
            suffix[i] = suffix[i + 1] + arr[i];
            max_suffix = max(max_suffix, suffix[i]);
        }
        int max_sum = 0;
        int lastMax = 0;
        for (int i = 0; i < arr.size(); i++)
        {
            lastMax = max(lastMax + arr[i], arr[i]);
            max_sum = max(max_sum, lastMax);
        }
        if (k == 1)
        {
            return max_sum;
        }
        else if (prefix[arr.size()] > 0)
        {
            return ((long long)prefix[arr.size()] * (k - 2) + max_prefix + max_suffix) % mod;
        }
        else
        {
            return max((max_prefix + max_suffix), max_sum) % mod;
        }
    }
};

int main()
{
    cout << "Code1191" << endl;
    Solution s;
    std::vector<int> arr = {-5, 4, -4, -3, 5, -3};
    cout << s.kConcatenationMaxSum(arr, 3) << endl;
    return 0;
}